208C - Police Station - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define F(i, a, b) for (int i = a; i < b; i++)
#define FE(i, a, b) for (int i = a; i <= b; i++)
#define FR(i, a, b) for (int i = a; i > b; i--)
#define FRE(i, a, b) for (int i = a; i >= b; i--)
#define ll                                                                     \
  long long // data types used often, but you don't want to type them time by
            // time
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOREACH(i, t)                                                          \
  for (auto i = t.begin(); i != t.end(); i++) // traverse an STL data structure
#define ALL(c) (c).begin(), (c).end() // handy for function like "sort()"
#define IND(e, arr) find(begin(arr), end(arr), e) - begin(arr)
#define IOS                                                                    \
  ios_base::sync_with_stdio(0); // to synchronize the input of cin and scanf
#define INF 1001001001
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef vector<vector<int>> vvi;
typedef vector<bool> vb;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int n, m, x, y;

int main() {
  cin >> n >> m;
  vvi dist = vvi(n, vi(n, INF));
  F(i, 0, m) {
    cin >> x >> y;
    dist[x - 1][y - 1] = dist[y - 1][x - 1] = 1;
  }
  vvi connected = dist;
  F(i, 0, n) {
    F(j, 0, n) {
      if (connected[i][j] == INF)
        connected[i][j] = 0;
    }
  }

  F(k, 0, n) {
    F(i, 0, n) {
      F(j, 0, n) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); }
    }
  }
  F(i, 0, n) { dist[i][i] = 0; }

  vector<ll> cnt(n, 0), cnt2(n, 0);
  vii distances(n);
  F(i, 0, n) { distances[i] = {dist[0][i], i}; }
  sort(ALL(distances));
  cnt[0] = 1;
  bitset<100> visited;
  for (auto &x : distances) {
    visited.set(x.second);
    // cout << x.second << endl;
    F(j, 0, n) {
      if (!connected[x.second][j] || visited.test(j))
        continue;
      if (dist[0][x.second] + 1 + dist[j][n - 1] == dist[0][n - 1]) {
        cnt[j] += cnt[x.second];
      }
    }
  }
  F(i, 0, n) { distances[i] = {dist[n - 1][i], i}; }
  sort(ALL(distances));
  cnt2[n - 1] = 1;
  visited.reset();
  for (auto &x : distances) {
    visited.set(x.second);
    // cout << x.second << endl;
    F(j, 0, n) {
      if (!connected[x.second][j] || visited.test(j))
        continue;
      if (dist[n - 1][x.second] + 1 + dist[j][0] == dist[0][n - 1]) {
        cnt2[j] += cnt2[x.second];
      }
    }
  }
  ll maxi = 0;
  F(i, 1, n - 1) {
    ll tmp = 0;
    F(j, 0, n) {
      if (connected[i][j] &&
          dist[0][i] + 1 + dist[j][n - 1] == dist[0][n - 1]) {
        tmp += cnt[i] * cnt2[j];
      }
    }
    maxi = max(maxi, tmp);
  }
  printf("%.08lf\n", max(2.0 * maxi / cnt[n - 1], 1.0));
  return 0;
}